A programmable digital computer provides a flexible environment to simulate complex systems such as a multi-layer protocol or a communication network. A system model, once described, can be analyzed extensively and then the model may be modified to study the effects of perturbations. Although there are numerous methods of simulation, they depart primarily in their details, not in their general characteristics. Most general purpose simulators exhibit the following essential characteristics: (1) the model, once activated from an initial condition, is represented by a series of events corresponding to changes in states of the model and, oftentimes, these changes are associated with particular instants of time in a simulated time environment; and (2) simulated time must not be affected by the time required to compute the events or state changes.
In order to make some simulations tractable, quite often it is required that parallel processing be utilized for complex models. With parallel processing, computations of the changing states of the model are subdivided into tasks that are suitable for execution in parallel. An inherent problem in the parallel approach, however, is the difficulty in ensuring that the computations, which are distributed among the processors for autonomous execution, are properly synchronized or aligned. As a simple example, it is supposed that two processors are executing in parallel and the first processor requires the results from the second processor. Then, the simulation must be arranged so that the second processor communicates its results to the first processor before the second processor may continue its computations; this is particularly important if the second processor completes its execution before the execution of the first processor is completed.
In one conventional approach to solve this state alignment problem, software techniques have been utilized. Scheduling, signaling and checking algorithms required to preserve the execution sequence generate considerable overhead which substantially reduces the efficiency gained through parallel processing.
To alleviate the problems associated with software approaches, circuit arrangements have recently been proposed as an alternative solution. Representative of the most recent conventional circuit arrangements is U.S. Pat. No. 4,392,196 issued to Glenn et al.
Glenn et al discloses means for aligning simulated time between the individual processors in a multiple processor emulation system. This is accomplished by using a time window established within each processor and a master timing signal. During execution, any processor which is operating within the time frame of the common window may continue execution. Any processor which falls behind the window must halt the advance of the master signal until the processor can execute long enough to move back into the window. Any processor which moves ahead of the window must enter an idle state until the master signal advances enough for the processing element to move back into the window.
In Glenn et al, it is necessary to choose a set of parameters that scale the operation of the synchronization mechanism according to the system that is being modeled. This can be done effectively as long as the duration of tasks executing by the individual processors, measured in units of simulated time, does not vary over a broad range. When judiciously selected, simulated time advances at a rate that mitigates processor idle time and thus contributes to execution efficiency. However, a less than judicious selection can result in poor execution efficiency and even to a loss of time alignment.
The resolution of the time alignment mechanism in Glenn et al varies in correspondence to two parameters, namely, the window span and the increment of simulated time upon each advance of the master signal. The constraints on these parameters are generally as follows. The increment must be no greater than the length of time of the smallest task being modeled. The window span must be no greater than the smallest duration of time to be aligned or synchronized. A conservative way to use the system of Glenn et al is to maximize its resolution by choosing the smallest possible values for the parameters. However, this maximizes the number of master signal transitions required to advance simulated time and, thereby, reduces execution efficiency to a minimum since the processors will spend more time idling as simulated time is advanced incrementally through the inevitable periods of inactivity. In a simulation that inherently has long periods of simulated time between state changes, the reduction of efficiency is substantial. A simulation that includes long periods between clusters of state changes dictates a small increment parameter and, accordingly, suffers low execution efficiency.
Thus, Glenn et al require careful study of the simulation model and judicious choice of parameters to strike an appropriate balance between alignment resolution and execution efficiency. The number of choices vary as the number of systems to be modeled is varied.